// 正常的查找
// #### 0. 不用算法：用js常见的方法
// const A = [1,2,3,4,6,7,9]
// const x = 8 
// const b = A.find(a => a > x)
// if( b === undefined) {
//     A.push(x)
// } else {
//     const idx = A.indexOf(b)
//     A.splice(idx,0,x)
// }
// #### 1. 如何在一个有序数组内插入一个新的值，并保证有序数据保持有序状态
// const A = [1,2,3,4,6,7,9]
// const x = 8 
// function insert(A, x) {
//     // p指向下一个需要比较的元素
//     // p+1指向空位
//     let p = A.length - 1
//     while(A[p] > x){
//         A[p+1] = A[p]
//         p--
//     }
//     A[p+1] = x
//     console.log(A)
// }
// insert(A,x)


// #### 2. 插入排序算法
const A = [1,2,3,4,6,7,9]
const x = 8 
function insert(A, i, x) {
    // p指向下一个需要比较的元素
    // p+1指向空位
    let p = i - 1
    // 最好的情况：已经是正序，则执行 N - 1
    // 最坏的情况：已经是倒序，则1+2+3+...+N-1 = (N²-N)/2 
    while(p >= 0 && A[p] > x){  
        A[p+1] = A[p]
        p--
    }
    A[p+1] = x
    console.log(A)
}

function insert_sort(A){
    for(let i = 0; i< A.length; i++) {  //循环 N-1
        insert(A,i, A[i])
    }
}
